package likou.offer;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Info: TODO 这个数据结构用的很棒
 * @Author: 唐小尊
 * @Date: 2020/8/23  19:47
 */
public class _41_niubi {
    static Queue<Integer> left;
    static Queue<Integer> right;
    static boolean singular = false;;

    /** initialize your data structure here. */
    public static void MedianFinder() {
        left = new PriorityQueue<>((v1, v2)->v2-v1);
        right = new PriorityQueue<>();
    }

    public static void addNum(int num) {
        // 每次时间复杂度都是logN
        if(singular){
            singular = false;
            if (!left.isEmpty() && left.peek() > num){
                right.offer(left.poll());
                left.offer(num);
            } else{
                right.offer(num);
            }
        } else {
            singular = true;
            if (!right.isEmpty() && right.peek() < num){
                left.offer(right.poll());
                right.offer(num);
            } else{
                left.offer(num);
            }
        }
    }

    public static double findMedian() {
        if (singular){
            return left.peek().doubleValue();
        }
        return (double)(left.peek() + right.peek()) / 2;
    }
    public static void main(String[] args) {
        MedianFinder();
        addNum(6);
        System.out.println(findMedian());
        addNum(10);
        System.out.println(findMedian());
        addNum(2);
        System.out.println(findMedian());
        addNum(6);
        System.out.println(findMedian());
        addNum(5);
        System.out.println(findMedian());
        addNum(0);
        System.out.println(findMedian());
        addNum(6);
        System.out.println(findMedian());
        addNum(3);
        System.out.println(findMedian());
        addNum(1);
        System.out.println(findMedian());
        addNum(0);
        System.out.println(findMedian());
        addNum(0);
        System.out.println(findMedian());

    }
}
